1. Field of the Invention
This invention relates generally to a secure physical random bit generator apparatus and method for generating random bits and, more particularly, it relates to a secure physical random bit generator apparatus and method for generating random bits using computer storage devices as a source of randomness.
2. Background of Related Art
As one of many uses, randomness and randomness generation are a central aspect of cryptography. In cryptography, randomness is paramount for key randomness generation, is necessary in many encryption algorithms and interactive proofs, and useful for boosting the efficiency of algorithms. Randomness is the pillar on which anonymity rests, and protocol soundness often requires access to a source of random bits.
It has been proven that if a one-way function exists, then, given a random seed, it is possible to generate more randomness (a polynomial amount in the length of the seed). A function that amplifies randomness in this manner is called a pseudo-random generator. It is also known that if the underlying hardness assumption holds (i.e., that a particular function cannot be inverted in polynomial time in the length of its security parameter) then it is impossible to predict the next bit to be output by the pseudo-random generator with a probability non-negligibly better than 1/2.
It should be noted that the ability to predict the next output bit holds only if the seed is unknown to the adversary. Therefore, randomness (in the form of the short seed) is necessary in order to produce more randomness.
In commercial cryptographic packages, the seed is generally supplied by the user. One approach for use by the user is to base the seed on timing information between key strokes during a period of several minutes during which the user "bangs the keyboard". Allegedly, this produces a random seed, but is rather inconvenient to the user. Thus, more automated methods have been suggested based on physical phenomena having a large portion of unpredictability.
For instance, one such method uses the time between observed emissions from a radioactive material. Another method measures the frequency instability of an oscillator. Both of these methods require the introduction of new devices, i.e., the radioactive material and the noisy transistor, respectively, and the measuring mechanisms to observe these devices. Other methods include the quantum-mechanical noise in transistors and lava lamp blobs. Needless to say, additional devices and mechanisms increase costs and new potential weaknesses, particularly if the device or meter stops working as designed.
Accordingly, there exists a need for a secure physical random bit generator apparatus and method for generating random bits which does not require user involvement, is not predictable, and is not manipulatable. Additionally, a need exists for a secure physical random bit generator apparatus and method for generating random bits which does not require any new equipment or any modifications to a computer'operating system. Furthermore, there exists a need for a secure physical random bit generator apparatus and method for generating random bits which allows the user to easily determine whether the generator is functioning correctly. Further yet, a need exists for a secure physical random bit generator apparatus and method for generating random bits which is based on a well-studied physical phenomenon thereby establishing an assurance of the level of randomness for the user.